home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 7 / Apprentice-Release7.iso / Source Code / C / Applications / POV-Ray 3.0.2 / src / MacSource / LnkLst.c < prev    next >
Encoding:
C/C++ Source or Header  |  1996-07-14  |  7.4 KB  |  314 lines  |  [TEXT/CWIE]
  1. /*==============================================================================
  2. Project:    POV
  3.  
  4. Version:    3
  5.  
  6. File:    LnkLst.c
  7.  
  8. Description:
  9. Routines to handle linked lists
  10. ------------------------------------------------------------------------------
  11. Author:
  12.     Eduard [esp] Schwan
  13. ------------------------------------------------------------------------------
  14.     from Persistence of Vision(tm) Ray Tracer
  15.     Copyright 1996 Persistence of Vision Team
  16. ------------------------------------------------------------------------------
  17.     NOTICE: This source code file is provided so that users may experiment
  18.     with enhancements to POV-Ray and to port the software to platforms other 
  19.     than those supported by the POV-Ray Team.  There are strict rules under
  20.     which you are permitted to use this file.  The rules are in the file
  21.     named POVLEGAL.DOC which should be distributed with this file. If 
  22.     POVLEGAL.DOC is not available or for more info please contact the POV-Ray
  23.     Team Coordinator by leaving a message in CompuServe's Graphics Developer's
  24.     Forum.  The latest version of POV-Ray may be found there as well.
  25.  
  26.     This program is based on the popular DKB raytracer version 2.12.
  27.     DKBTrace was originally written by David K. Buck.
  28.     DKBTrace Ver 2.0-2.12 were written by David K. Buck & Aaron A. Collins.
  29. ------------------------------------------------------------------------------
  30. Change History:
  31. ==============================================================================*/
  32.  
  33.  
  34. #define LNKLST_C
  35.  
  36. #include "LnkLst.h"
  37.  
  38. #include <types.h>    // Ptr
  39. #include <memory.h>    // disposeptr
  40. #include <StdDef.h>
  41.  
  42.  
  43. // House keeping
  44.  
  45. // ------------------------------------------------------------
  46. LLHeadPtr LLCreateList(short MaxElements)
  47.     {
  48.     LLHeadPtr LL;
  49.  
  50.     // Create new list head record
  51.     LL = (LLHeadPtr)NewPtr(sizeof(LLHeadRec));
  52.  
  53.     // Initialize fields
  54.     if (LL)
  55.         {
  56.         LL->fMaxElements = MaxElements;
  57.         LL->fNumElements = 0;
  58.         LL->fFirstElement = NULL;
  59.         LL->fLastElement = NULL;
  60.         }
  61.  
  62.     // return new LL to user
  63.     return LL;
  64.     } // LLCreateList
  65.  
  66.  
  67. // ------------------------------------------------------------
  68. void LLDestroyList(LLHeadPtr LL)
  69.     {
  70.     if (LL)
  71.         {
  72.         // Delete all elements from the list
  73.         LLDeleteAllElements(LL);
  74.  
  75.         // Now delete the header record itself
  76.         DisposePtr((Ptr)LL);
  77.         }
  78.     } // LLDestroyList
  79.  
  80.  
  81. // ------------------------------------------------------------
  82. void LLDeleteAllElements(LLHeadPtr LL)
  83.     {
  84.     if (LL)
  85.         {
  86.         // delete each one
  87.         while (LLGetNumElements(LL) > 0)
  88.             {
  89.             LLDeleteElementByIndex(LL, 1);
  90.             }
  91.         }
  92.     } // LLDeleteAllElements
  93.  
  94.  
  95. // Add
  96.  
  97. // ------------------------------------------------------------
  98. void LLAddElementByIndex(LLHeadPtr LL, void * DataPtr, short Index)
  99.     {
  100.     LLElPtr    newEl;
  101.     LLElPtr    oldEl;
  102.  
  103.     if (LL)
  104.         {
  105.         // allocate a new element
  106.         newEl = (LLElPtr)NewPtr(sizeof(LLElRec));
  107.         // initialize fields
  108.         newEl->fNext = NULL;
  109.         newEl->fPrev = NULL;
  110.         newEl->fData = DataPtr;
  111.         // add it to list
  112.         if (LLGetNumElements(LL) == 0)
  113.             { // add to empty list
  114.             LL->fFirstElement = newEl;
  115.             LL->fLastElement  = newEl;
  116.             LL->fNumElements++;
  117.             }
  118.         else
  119.             { // add to non-empty list
  120.             if (Index <= 1)
  121.                 { // add to beginning of list
  122.                 newEl->fNext            = LL->fFirstElement;
  123.                 LL->fFirstElement->fPrev = newEl;
  124.                 LL->fFirstElement        = newEl;
  125.                 }
  126.             else if (Index > LLGetNumElements(LL))
  127.                 { // add to end of list
  128.                 newEl->fPrev           = LL->fLastElement;
  129.                 LL->fLastElement->fNext = newEl;
  130.                 LL->fLastElement        = newEl;
  131.                 }
  132.             else
  133.                 { // add to middle of list
  134.                 short k;
  135.                 oldEl = LL->fFirstElement;
  136.                 for (k=1; (k<Index) && oldEl; k++)
  137.                     oldEl = (LLElPtr)oldEl->fNext;
  138.                 if (oldEl) // safe to reference it?
  139.                     {
  140.                     newEl->fPrev        = oldEl->fPrev;
  141.                     newEl->fNext        = oldEl;
  142.                     oldEl->fPrev        = newEl;
  143.                     ((LLElPtr)oldEl->fPrev)->fNext = newEl;
  144.                     }
  145.                 }
  146.             LL->fNumElements++;
  147.             }
  148.         }
  149.     } // LLAddElementByIndex
  150.  
  151.  
  152. // ------------------------------------------------------------
  153. void LLAppendElement(LLHeadPtr LL, void * DataPtr)
  154.     {
  155.     if (LL)
  156.         {
  157.         LLAddElementByIndex(LL, DataPtr, LLGetNumElements(LL)+1);
  158.         }
  159.     } // LLAppendElement
  160.  
  161.  
  162. // ------------------------------------------------------------
  163. void LLDeleteElementByIndex(LLHeadPtr LL, short Index)
  164.     {
  165.     LLElPtr    oldEl = NULL;
  166.     if (LL)
  167.         {
  168.         if (LLGetNumElements(LL) > 0)
  169.             { // non-empty list, OK to delete
  170.             if (LLGetNumElements(LL) == 1)
  171.                 { // only one on list
  172.                 oldEl            = LL->fFirstElement;
  173.                 LL->fFirstElement = NULL;
  174.                 LL->fLastElement  = NULL;
  175.                 }
  176.             else
  177.                 { // else more than one on list
  178.                 if (Index == 1)
  179.                     { // first one on list
  180.                     oldEl               = LL->fFirstElement;
  181.                     ((LLElPtr)oldEl->fNext)->fPrev = NULL;
  182.                     LL->fFirstElement    = (LLElPtr)oldEl->fNext;
  183.                     }
  184.                 else if (Index == LLGetNumElements(LL))
  185.                     { // last one on list
  186.                     oldEl                   = LL->fLastElement;
  187.                     LL->fLastElement        = (LLElPtr)oldEl->fPrev; // move back
  188.                     LL->fLastElement->fNext = NULL;
  189.                     }
  190.                 else if ((Index > 1) && (Index < LLGetNumElements(LL)))
  191.                     { // middle of list
  192.                     short k;
  193.                     oldEl = LL->fFirstElement;
  194.                     for (k=1; (k<Index) && oldEl; k++)
  195.                         oldEl = (LLElPtr)oldEl->fNext;
  196.                     }
  197.                 } // else more than one on list
  198.             // if found, delete it
  199.             if (oldEl)
  200.                 {
  201.                 DisposePtr((Ptr)oldEl);
  202.                 LL->fNumElements--;
  203.                 }
  204.             } // non-empty list, OK to delete
  205.         }
  206.     } // LLDeleteElementByIndex
  207.  
  208.  
  209. // Gets
  210.  
  211. // ------------------------------------------------------------
  212. short LLGetMaxElements(LLHeadPtr LL)
  213.     {
  214.     if (!LL)
  215.         return 0;
  216.     else
  217.         return LL->fMaxElements;
  218.     } // LLGetMaxElements
  219.  
  220.  
  221. // ------------------------------------------------------------
  222. short LLGetNumElements(LLHeadPtr LL)
  223.     {
  224.     if (!LL)
  225.         return 0;
  226.     else
  227.         return LL->fNumElements;
  228.     } // LLGetNumElements
  229.  
  230.  
  231. // ------------------------------------------------------------
  232. void * LLGetElementByIndex(LLHeadPtr LL, short Index)
  233.     {
  234.     LLElPtr    theEl = NULL;
  235.     if (LL)
  236.         {
  237.         short k;
  238.         theEl = LL->fFirstElement;
  239.         for (k=1; (k<Index) && theEl; k++)
  240.             theEl = (LLElPtr)theEl->fNext;
  241.         }
  242.     if (theEl)
  243.         return theEl->fData;
  244.     else
  245.         return NULL;
  246.     } // LLGetElementByIndex
  247.  
  248.  
  249. // ------------------------------------------------------------
  250. #ifdef LLTEST
  251. // ------------------------------------------------------------
  252.  
  253. void LLTest(void)
  254.     {
  255.     char *    p;
  256.     short    anError = 0;
  257.     short    k;
  258.     LLHeadPtr    LL = NULL;
  259.     
  260.     // pathological cases
  261.     LLDeleteAllElements(LL);
  262.     LLDestroyList(LL);
  263.     LLAddElementByIndex(LL, NULL, 1);
  264.     LLDeleteElementByIndex(LL, 1);
  265.     p = LLGetElementByIndex(LL, 1);
  266.     k = LLGetNumElements(LL);
  267.     k = LLGetMaxElements(LL);
  268.  
  269.     // for real...
  270.     LL = LLCreateList(10);
  271.     if (LL == NULL)
  272.         anError = -1;
  273.     LLAddElementByIndex(LL, (char*)3, 1); // first ever
  274.     LLAddElementByIndex(LL, (char*)1, 1); // insert at head
  275.     LLAddElementByIndex(LL, (char*)4, 3); // append last
  276.     LLAddElementByIndex(LL, (char*)2, 2); // add in middle
  277.  
  278.     p = LLGetElementByIndex(LL, 1);
  279.     if ((long)p != 1)
  280.         anError = 1;
  281.     p = LLGetElementByIndex(LL, 2);
  282.     if ((long)p != 2)
  283.         anError = 2;
  284.     p = LLGetElementByIndex(LL, 3);
  285.     if ((long)p != 3)
  286.         anError = 3;
  287.     p = LLGetElementByIndex(LL, 4);
  288.     if ((long)p != 4)
  289.         anError = 4;
  290.     p = LLGetElementByIndex(LL, 6);
  291.  
  292.     k = LLGetNumElements(LL);
  293.     if (k != 4)
  294.         anError = -4;
  295.     k = LLGetMaxElements(LL);
  296.     if (k != 10)
  297.         anError = 10;
  298.  
  299.     LLDeleteElementByIndex(LL, 5); // bad
  300.     LLDeleteElementByIndex(LL, 0);
  301.  
  302.     LLDeleteElementByIndex(LL, 4);
  303.     LLDeleteElementByIndex(LL, 1);
  304.     LLDeleteElementByIndex(LL, 2);
  305.     LLDeleteElementByIndex(LL, 1);
  306.  
  307.     LLDeleteAllElements(LL);
  308.     LLDestroyList(LL);
  309.     } // LLTest
  310.  
  311. #endif
  312.  
  313.  
  314.